{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2023 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# vrp_time_windows_per_vehicles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/constraint_solver/vrp_time_windows_per_vehicles.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/ortools/constraint_solver/samples/vrp_time_windows_per_vehicles.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "Vehicles Routing Problem (VRP) with Time Window (TW) per vehicle.\n",
    "\n",
    " All time are in minutes using 0am as origin\n",
    " e.g. 8am = 480, 11am = 660, 1pm = 780 ...\n",
    "\n",
    " We have 1 depot (0) and 16 locations (1-16).\n",
    " We have a fleet of 4 vehicles (0-3) whose working time is [480, 1020] (8am-5pm)\n",
    " We have the distance matrix between these locations and depot.\n",
    " We have a service time of 25min at each location.\n",
    "\n",
    " Locations are duplicated so we can simulate a TW per vehicle.\n",
    " location: [01-16] vehicle: 0 TW: [540, 660] (9am-11am)\n",
    " location: [17-32] vehicle: 1 TW: [660, 780] (11am-1pm)\n",
    " location: [33-48] vehicle: 2 TW: [780, 900] (1pm-3pm)\n",
    " location: [49-64] vehicle: 3 TW: [900, 1020] (3pm-5pm)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.constraint_solver import routing_enums_pb2\n",
    "from ortools.constraint_solver import pywrapcp\n",
    "\n",
    "\n",
    "def create_data_model():\n",
    "    \"\"\"Stores the data for the problem.\"\"\"\n",
    "    data = {}\n",
    "    data['time_matrix'] = [\n",
    "        [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],\n",
    "        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],\n",
    "        [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],\n",
    "        [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],\n",
    "        [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],\n",
    "        [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],\n",
    "        [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],\n",
    "        [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],\n",
    "        [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],\n",
    "        [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],\n",
    "        [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],\n",
    "        [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],\n",
    "        [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],\n",
    "        [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],\n",
    "        [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],\n",
    "        [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],\n",
    "        [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],\n",
    "    ]\n",
    "    data['num_vehicles'] = 4\n",
    "    data['depot'] = 0\n",
    "    return data\n",
    "\n",
    "\n",
    "def print_solution(manager, routing, assignment):\n",
    "    \"\"\"Prints solution on console.\"\"\"\n",
    "    print(f'Objective: {assignment.ObjectiveValue()}')\n",
    "    # Display dropped nodes.\n",
    "    dropped_nodes = 'Dropped nodes:'\n",
    "    for index in range(routing.Size()):\n",
    "        if routing.IsStart(index) or routing.IsEnd(index):\n",
    "            continue\n",
    "        if assignment.Value(routing.NextVar(index)) == index:\n",
    "            node = manager.IndexToNode(index)\n",
    "            if node > 16:\n",
    "                original = node\n",
    "                while original > 16:\n",
    "                    original = original - 16\n",
    "                dropped_nodes += f' {node}({original})'\n",
    "            else:\n",
    "                dropped_nodes += f' {node}'\n",
    "    print(dropped_nodes)\n",
    "    # Display routes\n",
    "    time_dimension = routing.GetDimensionOrDie('Time')\n",
    "    total_time = 0\n",
    "    for vehicle_id in range(manager.GetNumberOfVehicles()):\n",
    "        plan_output = f'Route for vehicle {vehicle_id}:\\n'\n",
    "        index = routing.Start(vehicle_id)\n",
    "        start_time = 0\n",
    "        while not routing.IsEnd(index):\n",
    "            time_var = time_dimension.CumulVar(index)\n",
    "            node = manager.IndexToNode(index)\n",
    "            if node > 16:\n",
    "                original = node\n",
    "                while original > 16:\n",
    "                    original = original - 16\n",
    "                plan_output += f'{node}({original})'\n",
    "            else:\n",
    "                plan_output += f'{node}'\n",
    "            plan_output += f' Time:{assignment.Value(time_var)} -> '\n",
    "            if start_time == 0:\n",
    "                start_time = assignment.Value(time_var)\n",
    "            index = assignment.Value(routing.NextVar(index))\n",
    "        time_var = time_dimension.CumulVar(index)\n",
    "        node = manager.IndexToNode(index)\n",
    "        plan_output += f'{node} Time:{assignment.Value(time_var)}\\n'\n",
    "        end_time = assignment.Value(time_var)\n",
    "        duration = end_time - start_time\n",
    "        plan_output += f'Duration of the route:{duration}min\\n'\n",
    "        print(plan_output)\n",
    "        total_time += duration\n",
    "    print(f'Total duration of all routes: {total_time}min')\n",
    "\n",
    "\n",
    "def main():\n",
    "    \"\"\"Solve the VRP with time windows.\"\"\"\n",
    "    # Instantiate the data problem.\n",
    "    data = create_data_model()\n",
    "\n",
    "    # Create the routing index manager.\n",
    "    manager = pywrapcp.RoutingIndexManager(\n",
    "        1 + 16 * 4,  # number of locations\n",
    "        data['num_vehicles'],\n",
    "        data['depot'])\n",
    "\n",
    "    # Create Routing Model.\n",
    "    routing = pywrapcp.RoutingModel(manager)\n",
    "\n",
    "\n",
    "    # Create and register a transit callback.\n",
    "    def time_callback(from_index, to_index):\n",
    "        \"\"\"Returns the travel time between the two nodes.\"\"\"\n",
    "        # Convert from routing variable Index to time matrix NodeIndex.\n",
    "        from_node = manager.IndexToNode(from_index)\n",
    "        to_node = manager.IndexToNode(to_index)\n",
    "        # since our matrix is 17x17 map duplicated node to original one to\n",
    "        # retrieve the travel time\n",
    "        while from_node > 16:\n",
    "            from_node = from_node - 16\n",
    "        while to_node > 16:\n",
    "            to_node = to_node - 16\n",
    "        # add service of 25min for each location (except depot)\n",
    "        service_time = 0\n",
    "        if from_node != data['depot']:\n",
    "            service_time = 25\n",
    "        return data['time_matrix'][from_node][to_node] + service_time\n",
    "\n",
    "    transit_callback_index = routing.RegisterTransitCallback(time_callback)\n",
    "\n",
    "    # Define cost of each arc.\n",
    "    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\n",
    "\n",
    "    # Add Time Windows constraint.\n",
    "    time = 'Time'\n",
    "    routing.AddDimension(\n",
    "        transit_callback_index,\n",
    "        0,  # allow waiting time (0 min)\n",
    "        1020,  # maximum time per vehicle (9 hours)\n",
    "        False,  # Don't force start cumul to zero.\n",
    "        time)\n",
    "    time_dimension = routing.GetDimensionOrDie(time)\n",
    "    # Add time window constraints for each location except depot.\n",
    "    for location_idx in range(17):\n",
    "        if location_idx == data['depot']:\n",
    "            continue\n",
    "        # Vehicle 0 location TW: [9am, 11am]\n",
    "        index_0 = manager.NodeToIndex(location_idx)\n",
    "        time_dimension.CumulVar(index_0).SetRange(540, 660)\n",
    "        routing.VehicleVar(index_0).SetValues([-1, 0])\n",
    "\n",
    "        # Vehicle 1 location TW: [11am, 1pm]\n",
    "        index_1 = manager.NodeToIndex(location_idx + 16 * 1)\n",
    "        time_dimension.CumulVar(index_1).SetRange(660, 780)\n",
    "        routing.VehicleVar(index_1).SetValues([-1, 1])\n",
    "\n",
    "        # Vehicle 2 location TW: [1pm, 3pm]\n",
    "        index_2 = manager.NodeToIndex(location_idx + 16 * 2)\n",
    "        time_dimension.CumulVar(index_2).SetRange(780, 900)\n",
    "        routing.VehicleVar(index_2).SetValues([-1, 2])\n",
    "\n",
    "        # Vehicle 3 location TW: [3pm, 5pm]\n",
    "        index_3 = manager.NodeToIndex(location_idx + 16 * 3)\n",
    "        time_dimension.CumulVar(index_3).SetRange(900, 1020)\n",
    "        routing.VehicleVar(index_3).SetValues([-1, 3])\n",
    "\n",
    "        # Add Disjunction so only one node among duplicate is visited\n",
    "        penalty = 100_000  # Give solver strong incentive to visit one node\n",
    "        routing.AddDisjunction([index_0, index_1, index_2, index_3], penalty, 1)\n",
    "\n",
    "    # Add time window constraints for each vehicle start node.\n",
    "    depot_idx = data['depot']\n",
    "    for vehicle_id in range(data['num_vehicles']):\n",
    "        index = routing.Start(vehicle_id)\n",
    "        time_dimension.CumulVar(index).SetRange(480, 1020)  # (8am, 5pm)\n",
    "\n",
    "    # Add time window constraints for each vehicle end node.\n",
    "    depot_idx = data['depot']\n",
    "    for vehicle_id in range(data['num_vehicles']):\n",
    "        index = routing.End(vehicle_id)\n",
    "        time_dimension.CumulVar(index).SetRange(480, 1020)  # (8am, 5pm)\n",
    "\n",
    "    # Instantiate route start and end times to produce feasible times.\n",
    "    for i in range(data['num_vehicles']):\n",
    "        routing.AddVariableMinimizedByFinalizer(\n",
    "            time_dimension.CumulVar(routing.Start(i)))\n",
    "        routing.AddVariableMinimizedByFinalizer(\n",
    "            time_dimension.CumulVar(routing.End(i)))\n",
    "\n",
    "    # Setting first solution heuristic.\n",
    "    search_parameters = pywrapcp.DefaultRoutingSearchParameters()\n",
    "    search_parameters.first_solution_strategy = (\n",
    "        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)\n",
    "    search_parameters.local_search_metaheuristic = (\n",
    "        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)\n",
    "    search_parameters.time_limit.FromSeconds(1)\n",
    "\n",
    "    # Solve the problem.\n",
    "    assignment = routing.SolveWithParameters(search_parameters)\n",
    "\n",
    "    # Print solution on console.\n",
    "    if assignment:\n",
    "        print_solution(manager, routing, assignment)\n",
    "    else:\n",
    "        print(\"no solution found !\")\n",
    "\n",
    "\n",
    "main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}
